IOI, Stockholm, 1994

  IOI. 13 (Castel)
 
                1   2   3   4   5   6   7 
                ***************************** 
               1*       *       *           * 
                ****   *****   *    **** 
               2*  *        *   *    *  *   * 
                *  *****    *****    ****   *  
               3*           *   *    *  *   * 
                *  **********   ******  *   * 
               4*  *                    *   * 
                ***************************** 
     Figura 1. (un sir de '*' semnifica un zid)
                               N 
                             W + E 
                               S 

    Figura 1 descrie harta unui castel. S[ se scrie un program care determin[:
1) Num[rul de camere din castel;
2) M[rimea (n module) a celei mai mari camere;
3) Ce perete (care sepr[ dou[ camere) trebuie eliminat din castel pentru a obine o camer[ c6t mai mare
    posibil.
Castelul este divizat ntr-o gril[ cu m linii i n coloane (m,n50) de module p[tratice.
Fiecare modul poate avea ntre 0 i 4 perei.
Intrare:
Harta este stocat[ n fiierul INPUT.TXT sub form[ de numere, cte un num[r pentru fiecare modul.
 - Primele dou[ linii ale fiierului dau num[rul de module pe direcia nord-sud respectiv num[rul de
module pe direcia est-vest.
 - Pe urm[toarele linii, fiecare modul este decsris de un num[r p (0p15); el este format din suma
numerelor: 1 (dac[ modulul are zid spre vest), 2 (zid spre nord), 4 (zid spre est) i 8 (zid spre sud).
Zidurile interioare sunt definite de dou[ ori (cte odat[ de fiecare modul).
De exemplu, modulul din poziia (1,1) are ziduri la vest, nord i sud, deci num[rul lui este 1+2+8=11.
 - castelul are cel puin dou[ camere.
 Pentru castelul din Figura 1, INPUT.TXT are forma:
4 
7 
11  6  11  6   3  10  6 
7   9  6  13   5  15  5 
1   10 12  7  13   7  5 
13  11 10  8  10  12  13
Ieire:
In fiierul OUTPUT.TXT, se scriu pe trei linii:
1) Num[rul de camere; 
2) suprafaa celei mai mari camere (m[surat[ n module); 
3) O sugestie care zid ar trebui eliminat pentru a obine din dou[ camere al[turate o camer[ cu suprafa[
maxim posibil[ (se vor scrie linia i coloana modulului de lng[ zid, urmate de punctul cardinal care
indic[ peretele).
   Pot fi mai multe variante, dar se cere numai una.
Pentru exemplul de sus:
5 
9 
4 1 E (este doar una din posibilit[i).
ceea ce reprezint[ pe desen:
                1   2   3   4   5   6   7 
                ***************************** 
               1*       *       *           * 
                ****   *****   *    ****    *
               2*  *        *   *    *  *   * 
                *  *****    *****    ****   * 
               3*           *   *    *  *   * 
                *  **********   ******  *   * 
               4*->*                    *   * 
                *****************************
  
===================================
Solutia 1 (Vlad Atanasiu):
uses crt,graph;
type leg=^modul;
     modul=record
           x,y,tip:byte;
           urm:leg;
           end;
     legf=^figura;
     figura=record
            arie:integer;
            lista:leg;
            urm:legf;
            end;
     sol=record
         x,y:integer;
         c:char;
         end;
var fprima,fstart,fcurent:legf;
    max_arie,camere,a,b,i,j:integer;
    m,tmp:leg;
    solutie:sol;
    g:array[1..100,1..100] of integer;

procedure analizeaza(x1,y1,x2,y2:integer);
{ analizeaza casutele aflate la x1,y1 si x2,y2, care au un zid intre ele; daca
  fac parte din camere diferite, calculeaza aria maxima si propune solutia }
var gasit1,gasit2:boolean;
    arie:integer;
    f1,f2:legf;
begin
fcurent:=fstart;
gasit1:=false;
gasit2:=false;
arie:=0;
while not(gasit1 and gasit2) do
      begin
      tmp:=fcurent^.lista;
      while tmp<>nil do
            begin
            if (not gasit1) and (tmp^.x=x1) and (tmp^.y=y1) then
               begin
               gasit1:=true;
               arie:=arie+fcurent^.arie;
               f1:=fcurent;
               end
            else if (not gasit2) and (tmp^.x=x2) and (tmp^.y=y2) then
                 begin
                 gasit2:=true;
                 arie:=arie+fcurent^.arie;
                 f2:=fcurent;
                 end;
            if (tmp^.urm<>nil) and (tmp^.urm^.x>11) then
               readln;
            tmp:=tmp^.urm;
            end;
      fcurent:=fcurent^.urm;
      end;
if (f1<>f2) and (arie>max_arie) then
   begin
   max_arie:=arie;
   solutie.x:=x1;
   solutie.y:=y1;
   if x1>x2 then solutie.c:='W'
   else solutie.c:='S';
   end;
end;

function vecini(a,b:modul):boolean;
{ intoarce true daca doua module sunt legate (nu au perete intre ele) }
var r:boolean;
begin
r:=false;
if a.y=b.y then
   begin
   if (a.x=b.x-1) and ((a.tip and 4)<>4) then r:=true;
   if (a.x=b.x+1) and ((b.tip and 4)<>4) then r:=true;
   end
else if a.x=b.x then
        begin
        if (a.y=b.y-1) and ((b.tip and 2)<>2) then r:=true;
        if (a.y=b.y+1) and ((a.tip and 2)<>2) then r:=true;
        end;
vecini:=r;
end;

function in_figura(c:legf;m:leg):boolean;
{ intoarce true daca m are vecini in figura c }
var ct:leg;
begin
ct:=c^.lista;
while (ct<>nil) and (not vecini(m^,ct^)) do
      ct:=ct^.urm;
in_figura:=(ct<>nil);
end;

begin
clrscr;
assign(input,'input.i13');
{assign(output,'op');
rewrite(output);}
reset(input);
readln(input,a);
readln(input,b);
fstart:=nil;
for i:=1 to a do
    begin
    for j:=1 to b do
        begin
        new(m);
        read(input,m^.tip);
        m^.x:=j;
        m^.y:=i;
        m^.urm:=nil;
        fprima:=nil;
        fcurent:=fstart;
        g[j,i]:=m^.tip;
        while fcurent<>nil do
              begin
              if in_figura(fcurent,m) then
                 if fprima=nil then
                    begin
                    { daca este prima figura in care este intalnit atunci il adauga la figura }
                    fprima:=fcurent;
                    tmp:=fprima^.lista;
                    while tmp^.urm<>nil do tmp:=tmp^.urm;
                    m^.urm:=fcurent^.lista;
                    fcurent^.lista:=m;
                    inc(fcurent^.arie);
                    end
                 else
                    begin
                    { daca nu este prima figura in care are vecini }
                    { adauga la fprima }
                    tmp^.urm:=fcurent^.lista;
                    while tmp^.urm<>nil do tmp:=tmp^.urm;
                    fprima^.arie:=fprima^.arie+fcurent^.arie;
                    { sterge fcurent }
                    fcurent^.lista:=nil;
                    fcurent^.arie:=0;
                    end;
              fcurent:=fcurent^.urm;
              end;
        if fprima=nil then
           begin
           { nu a fost adaugat la nici o figura }
           { creeaza o noua figura }
           new(fcurent);
           fcurent^.lista:=m;
           fcurent^.urm:=fstart;
           fstart:=fcurent;
           fstart^.arie:=1;
           end;
        end;
    readln(input);
    end;
max_arie:=0;
fcurent:=fstart;
camere:=0;
while fcurent<>nil do
      begin
      if fcurent^.arie>max_arie then max_arie:=fcurent^.arie;
      if fcurent^.arie>0 then inc(camere);
      fcurent:=fcurent^.urm;
      end;
writeln(' Camere : ',camere);
writeln(' Arie maxima : ',max_arie);
max_arie:=0;
for i:=1 to a do
    for j:=1 to b do
        begin
        { testarea se face numai pentru peretii din dreapta si jos, daca exista }
        if (i<a) and (g[j,i] and 8=8) then analizeaza(j,i,j,i+1);
        if (j<b) and (g[j,i] and 4=4) then analizeaza(j,i,j+1,i);
        end;
writeln(' Poate fi eliminat peretele ',solutie.x,' ',solutie.y,' ',solutie.c);
end.
=========================
Solutia 2 (Tom Verhoeff - Universitatea Eidhoven.Olanda)

    Un castel poate avea maxim 50*50=2500 module. Deci, toate datele de intrare pot fi citite din
fisier si stocate n program.
    Inainte de a decide cum s[ reprezent[ castelul n program, s[ vedem ce se cere.
Deci, fiind dat un castel, se solicit[ num[rul de camere, aria unei camere mari (s-a scris "aria unei camere
mari" i nu "aria celei mai mari camere" deoarece pot fi mai multe camere de arie maxim[), i un zid care
- dac[ este eliminat - conduce la obinerea unei camere ct mai mari posibil.
    S[ reformul[m aceasta mai precis.
   Spunem c[ dou[ module vecine sunt conectate dac[ nu exist[ nici un zid ntre ele.
   O camer[ este o mulime maximal[ de module conectate.
   Aria unei camere este num[rul de module pe care l conine.
   Vom defini potenialul unui zid interior ca fiind aria camerei obinut[ prin eliminarea lui. In acest fel,
al treilea el este de adetermina zidul cu potenial maxim (un cel mai bun zid).
    Un castel are maxim 2500 camere i aria maxim[ a unei camere este 2500 (de fapt 2499
deoarece castelul trebuie s[ aib[ minim dou[ camere, conform cerinelor problemei).
Exist[ maxim 4*50=200 ziduri exterioare i maxim (4*50*50-4*50)/2=4900 ziduri interioare.
    Un algoritm foarte cunoscut pentru determinarea camerelor se bazeaz[ pe colorarea modulelor n
culori diferite pentru camere diferite, cu o culoare pentru fiecare camer[.
Pornind cu culoarea num[rul 0 n modulul din nord vest al castelului, color[m cu aceeai culoare toate
modulele conectate cu el (n unul sau mai muli pai). Continu[m cu un modul necolorat folosind culoarea
1, i repet[m procedeul pn[ la colorarea tuturor modulelor.
    Pentru acest algoritm este necesr s[ travers[m modulele necolorate ale castelului i - pentru
fiecare modul - s[ g[sim modulele conectate cu el.
    Dup[ colorarea tuturor camerelor, exist[ mai multe metode de a determina ariile camerelor, aria
maxim[ i cel mai bun zid.

    Castelul are M linii i N coloane, cu 1M50,1N50. Vom num[ra liniile de la nord spre sud
i coloanele de la vest spre est, ambele numerot[ri ncepnd cu 1. Modulul de pe linia r i coloana c va
fi notat prin Map[r,c].
    Pentru fiecare modul vom da zidurile sale printr-o nregistrare (vest, nord, est, sud)
care desemneaz[ fiecare direcie; ordinea direciilor este inspirat[ de codificarea zidurilor n fiieurl de
intrare.
    Pentru fiecare modul vom reine i num[rul (culoarea) camerei. Toate aceste observaii conduc
la urm[toarele declaraii:
const
  MaxM=50;
  MaxN=50;
type
  Row=1..MaxM;
  Column=1..MaxN;
  Direction=(west, north, east, south);
  Module=record
    wall: array [Direction] of boolean;
    nr: integer; { numar camera, -1 daca nu se stie inca }
    end { Module };
var
  M: Row;
  N: Column;
  Map: array [Row, Column] of Module;

In nregistrarea Module am putea alege de asemenea o declarare:
    wall: set of Direction;
Alegerea uneia sau alteia din cele dou[ declar[ri depinde de operaiile care vor fi definite cu "wall".
Pentru acest[ problem[ ea nu conteaz[ foarte mult, dar iniializarea unui tablou boolean este ceva mai
simpl[.

    Citirea (i descrierea) unui castel;
    Urm[toarea procedur[ citete harta unui castel din fiierul de intrare 'inp'. Structura lui este dat[
de enunul problemei. Num[rul w care specific[ zidurile unui modul este decodificat prin trecerea lui n
baza 2.
procedure ReadInput;
  {citeste M, N, si Map; initializeaza numerele camerelor cu -1 }
var
  r: Row;
  c: Column;
  w: integer;
  d: Direction;
begin
   readln(inp,M,N);
   if Test then writeln('Numarul de linii: ', M:1, ', numarul de coloane
este: ', N:1);
   for r:=1 to M do begin
    for c:=1 to N do with Map[r,c] do begin
       read(inp,w); {w codifica zidurile modulului Map[r,c]}
       for d:=west to south do begin
         wall[d]:=odd(w);
         w := w div 2
                   end { pentru d };
      nr:=-1
             end { pentru c with Map };
    readln(inp)
       end {pentru r};
  if Test then writeln('Citeste datele de intrare');
end {ReadInput};

    Cnd scriem un program, este recomandabil s[ inser[m i unele teste care s[ ajute la verificarea
sa. De exmeplu, dup[ ce s-a citit castelul, el se poate reprezenta pe ecran sub o form[ ct mai sugestiv[
ca s[ se poat[ interpeta numerele codificate ale zidurilor.
Iat[ o procedur[ care face aa ceva:
procedure WriteCastle;
  {se scrie Map la iesire}
var
  r:Row;
  c:Column;
begin
  for c:=1 to N do with Map[1,c] do
    if wall[north] then write('_') else write('  ');
  writeln ;
  for r:=1 to M do begin
    for c:=1 to N do with Map[r,c] do begin
      if (c=1) then if wall[west] then write('|') else write(' ');
      if wall[south] then write('_') else write(' ');
      if wall[east] then write('|') else write(' ')
      end {pentru c with Map};
    writeln
    end { pentru r}
end {WriteCastle};

WriteCastle prezint[ harta castelului din exemplul problemei astfel:
                               _ _ _ _ _ _ _
                              |_  |_  |  _  |
                              | |_  |_| |_| |
                              |  _ _| |_| | |
                              |_|_ _ _ _ _|_|

    Determinarea num[rului de camere:
    Procedura PaintMap va parcurge modulele linie cu linie, de la nord spre sud, i pe fiecare linie,
de la vest spre est. Ori de cte ori vag[si un modul necolorat, ea va chema PaintRoom pentru a colora
modulul i toate modulele conectate cu el cu culoarea urm[toare. Culoarea este reprezentat[ printr-un
num[r ntreg.
PaintRoom este implementat[ foarte uor printr-o procedur[ recursiv[:
type
  RoomNumber=0..MaxM*MaxN;
var
  rooms:RoomNumber; {numarul camerelor colorate complet}
procedure PaintMap;
   {coloreaza harta}
procedure PaintRoom(r:Row; c:Column);
  {daca Map[r, c] este necolorat atunci se coloreaza impreuna cu toate
modulele conectate cu el}
begin
   with Map[r, c] do
      if nr=-1 then begin
        nr:=rooms;
        if not wall[west]  then PaintRoom(r,c-1);
        if not wall[north] then PaintRoom(r-1,c);
        if not wall[east]  then PaintRoom(r,c+1);
        if not wall[south] then PaintRoom(r+1,c)
                    end { if }
end {PaintRoom};
var
  r:Row;
  c:Column;
begin
  rooms:=0;
  for r:=1 to M do
    for c:=1 to N do
      if Map[r,c].nr=-1 then begin
        PaintRoom(r,c);
        rooms:=succ(rooms)
        end { if }
end {PaintMap};
Observaie: succ(v) este o notaie Pascal standard pentru succesorul lui v.
    Pentru fiecare modul necolorat PaintRoom este apelat odat[; el va colora acel modul i va
chema de cel mult patru ori PaintRoom. deci vor fi f[cute n total maxim 2500*(1+4)=12.500
apel[ri la procedura PaintRoom are made.
    Ar trebui ca aceasta s[ ne fac[ ateni la factorul linit[ de timp.
This should be feasible within the time limit (de fapt care este exact num[rul minim i cel maxim de
apel[ri ale procedurii pentru un castel 50x50 ?).
Pentru test[ri este convenabil s[ scriem o procedur[ care s[ scrie o hart[ colorat[ a castelului.
Aceasta este procedura WriteColors:
procedure WriteColors;
  { da la iesire harta culorilor}
var
  r:Row;
  c:Column;
begin
  for r:=1 to M do begin
    for c:=1 to N do write(Map[r,c].nr:2);
    writeln
    end {pentru r}
end {WriteColors};
    Dup[ apelul procedurii PaintMap, WriteColors prezint[ harta din exemplul de mai sus
astfel:
 0 0 1 1 2 2 2
 0 0 0 1 2 3 2
 0 0 0 4 2 4 2
 0 4 4 4 4 4 2

      Determinarea suprafaelor camerelor:
  Ariile camerelor pot fi calculate odat[ cu colorarea lor; deci pe parcurs se poate reine i aria maxim[.
Nu este necesar s[ p[str[m toate ariile calculate. Totui, pentru puncul urm[tor este convenabil
s[p[str[m ntr-un tablou suprafaa fiec[rei camere.
var
  area:array[RoomNumber] of integer; {area[n] reprezinta aria camerei cu
        numarul n}
  maxarea:integer; {camera de suprafata maxima}
      In loc de a modifica procedura PaintRoom pentru a calcula i ariile (cu riscul de a introduce
erori; vezi programul 2 de mai jos), vom scrie o procedur[ seprat[ MeasureRooms care va calcula ariile
tuturor camerelor, inclusiv aria maxim[.
procedure MeasureRooms;
  var r:Row;
  c:Column;
  n:RoomNumber;
begin
  for n:=0 to pred(rooms) do area[n]:=0;
  for r:=1 to M do
    for c:=1 to N do inc(area[Map[r,c].nr]);
  maxarea:=0;
  for n:=0 to pred(rooms) do
    if area[n]>maxarea then maxarea:=area[n]
end {MeasureRooms};
Observaie: pred(v) este o notaie Pascal Standard pentru predecesorul lui v, iar inc(v) este o notaie
Pascal pentru succesor.

      Determinarea unui zid de potenial maxim.
  Reamintim c[ potenialul unui zid interior este aria camerei format[ prin eliminarea acelui zid.
Pentru fiecare zid interior se poate determina uor potenialul lui. S[ observ[m c[ aceast[ arie nu este
neap[rat suma ariilor camerelor separate de zid (am f[cut aceast[ greeal[ n primul meu program). este
posibil ca de cele dou[ p[ri ale zidului s[ se afle aceeai camer[; n acest caz, nl[turarea lui nu creaz
o camer[ mai mare.
      Procedura urm[toare BestWall va considera toate zidurile interioare i va determina un zid cu
potenial maxim.
var
  bestrow:Row;
  bestcol:Column;
  bestdir:Direction;
procedure BestWall;
var
  r:Row;
  c:Column;
  maxp:integer;
procedure Update(k1,k2:RoomNumber; d:Direction);
var
  p:integer;
begin
   if k1=k2 then p:=area[k1] else p:=area[k1]+area[k2];
   if p>maxp then begin
      maxp:=p; bestrow:=r; bestcol:=c; bestdir:=d
      end {if}
end { Update };
begin
  maxp:=0;
  for r:=1 to M do
    for c:=1 to N do with Map[r,c] do begin
      if (r<>M) and wall[south] then Update(nr,Map[r+1,c].nr,south);
      if (c<>N) and wall[east] then Update(nr,Map[r,c+1].nr,east);
     end { pentru c with Map }
end {BestWall};
De remarcat c[ instruciunile if din interiorul ciclurilor for nu pot fi eliminate modificnd marginile
superioare n forma:
  for r := 1 to pred(M) do
    for c := 1 to pred(N) do ...
deoarece este posibil s[ fie omise unele ziduri interioare (zidurile sudice ale modulelor aflate la marginea
de est i zidurile estice din modulele cele mai la sud). Testul 3 verific[ aceast[ eroare; un r[spuns de
forma
9
36
1 1 S
va fi greit.
      Ne putem ntreba dac[ nu s-ar putea face un calcul mai eficient al potenialului maxim.
Verificarea tuturor zidurilor interioare pare extrem de obositor. Totui, volumul de munc[ din procedura
BestWall este de acelai ordin de m[rime ca citirea fiierului de intrare sau determinarea camerelor i
a ariilor lor. Bineneles, ar fi suficient s[ control[m numai camerele vecine (i nu toate zidurile
modulelor care le compun). colectarea i stocarea acestei informaii suplimentare este ns[ destul de
dificil[. De reinut c[ un zid de potenial maxim nu m[rginete neap[rat o camer[ de suprafa[
maxim[.

      Programe:
Programul 1 este complet.
Programul 2 este o variant[ n care aria camerei se determin[ n acelai timp cu colorarea ei.
-----------------
program ioi94day1prb2ver1(input,output,inp,out);
{Sectiune generala} 
const 
  Test=true;
var  
  inp,out:text; 
procedure Init; 
 begin 
  if Test then 
    writeln('IOI''94 - Day 1 - Problem 2: The Castle'); 
  assign(inp,'input.txt'); reset(inp);
  assign(out,'output.txt'); rewrite(out);
  if Test then writeln('Initialized') 
end {Init}; 
procedure Fini;
begin 
  close(inp); close(out)
end {Fini};
{Problema} 
const 
  MaxM=50; 
  MaxN=50; 
type
  Row=1..MaxM; 
  Column=1..MaxN;
  Direction=(west,north,east,south);
  Module=record 
    wall:array [Direction] of boolean; 
    nr:integer; {numar camera, -1 daca este nedeterminat}
end {Module};
var 
  M:Row; 
  N:Column; 
  Map:array [Row,Column] of Module;
procedure ReadInput; 
  {citeste M,N si Map; initializeaza numerele camerelor la -1}
  var r:Row; c:Column; w:integer; d: Direction;
begin 
  readln(inp,M,N);
  if Test then writeln('Numarul liniilor este ', M:1,', numarul
        coloanelor este ', N:1);
  for r:=1 to M do begin
    for c:=1 to N do with Map[r,c] do begin 
      read(inp,w); { w codifica zidurile din modulul Map[r,c]}
      for d:=west to south do begin 
        wall[d]:=odd(w);
        w:=w div 2 
          end { pentru d };
      nr:=-1
      end { pentru c with Map }; 
    readln(inp) 
         end { pentru r };
  if Test then writeln('Citeste datele de intrare'); 
end {ReadInput}; 
procedure WriteCastle; 
  {scrie harta}
var
  r:Row;
  c:Column;
begin 
  for c:=1 to N do with Map[1,c] do 
    if wall[north] then write(' _') else write('  ');
  writeln; 
  for r:=1 to M do begin
    for c:=1 to N do with Map[r,c] do begin
      if (c=1) then if wall[west] then write('|') else write(' ');
      if wall[south] then write('_') else write(' ');
      if wall[east] then write('|') else write(' ') 
      end { pentru c with Map };
    writeln 
    end {pentru r} 
end {WriteCastle};
type 
  RoomNumber=0..MaxM*MaxN;
var 
  rooms:RoomNumber; { numarul camerelor colorate complet}
procedure PaintMap;
  {colorarea hartii}
procedure PaintRoom(r:Row; c:Column);
 {daca Map[r,c] este necolorat, se coloreaza impreuna cu toate modulele
       conectate} 
begin 
   with Map[r,c] do
     if nr=-1 then begin
        nr:=rooms; 
        if not wall[west]  then PaintRoom(r,c-1); 
        if not wall[north] then PaintRoom(r-1,c); 
        if not wall[east]  then PaintRoom(r,c+1); 
        if not wall[south] then PaintRoom(r+1,c) 
        end {if}
end {PaintRoom};
var
  r:Row;
  c:Column;
begin 
  rooms:=0;
  for r:=1 to M do
    for c:=1 to N do
      if Map[r,c].nr=-1 then begin 
        PaintRoom(r,c);
        rooms:=succ(rooms) 
        end {if}
end {PaintMap};
procedure WriteColors;
  {scrie harta culorilor} 
var
  r:Row;
  c:Column;
begin 
  for r:=1 to M do begin 
    for c:=1 to N do write(Map[r,c].nr:2);
    writeln 
       end {pentru r} 
end {WriteColors};
var 
  area:array[RoomNumber] of integer; { area[n] este aria camerei cu
        numarul n} 
  maxarea:integer; {aria maxima a unei camere}
procedure MeasureRooms;
var
  r:Row;
  c:Column;
  n:RoomNumber;
begin 
  for n:=0 to pred(rooms) do area[n]:=0;
  for r:=1 to M do
    for c:=1 to N do
     inc(area[Map[r,c].nr]);
  maxarea:=0; 
  for n:=0 to pred(rooms) do 
    if area[n]>maxarea then maxarea:=area[n] 
end {MeasureRooms};
var 
  bestrow:Row;
  bestcol:Column;
  bestdir:Direction;
procedure BestWall;
var
  r:Row;
  c:Column;
  maxp:integer;
procedure Update(k1,k2:RoomNumber; d:Direction);
var
  p:integer;
begin 
   if k1=k2 then p:=area[k1] else p:=area[k1]+area[k2];
   if p>maxp then begin 
      maxp:=p; bestrow:=r; bestcol:=c; bestdir:=d
       end {if}
end {Update};
begin
  maxp:=0;
  for r:=1 to M do
    for c:=1 to N do with Map[r,c] do begin 
      if (r<>M) and wall[south] then Update(nr, Map[r+1,c].nr,south);
      if (c<>N) and wall[east] then Update(nr,Map[r,c+1].nr,east);
        end {pentru c with Map}
end {BestWall}; 
procedure ComputeAnswer;
begin 
  PaintMap; 
  if Test then WriteColors; 
  MeasureRooms; 
  BestWall 
end {ComputeAnswer}; 
procedure WriteOutput;
begin 
  if Test then begin 
    writeln('Numarul de camere=',rooms:1);
    writeln('Aria maximaa unei camere=',maxarea:1);
    writeln('Cel mai bun zid de eliminat=',bestrow:1,' ', bestcol:1,' ',
          bestdir:1) 
    end {if Test};
  writeln(out,rooms:1);
  writeln(out,maxarea:1); 
  write(out,bestrow:1,' ',bestcol:1, ' ');
 case bestdir of
    south: writeln(out, 'S'); 
    east: writeln(out, 'E'); 
    end {case} 
end {WriteOutput};
begin 
   Init; 
   ReadInput;
   if Test then WriteCastle;
   ComputeAnswer;
   WriteOutput;
   Fini 
end. 
-----------------------
Versiunea 2:
program ioi94day1prb2ver2(input,output,inp,out);
{ Sectiune generala}
const
  Test = true ;
var 
  inp, out: text ;
procedure Init ;
  begin
  if Test then
    writeln('IOI''94 - Day 1 - Problem 2: The Castle') ;
  assign(inp, 'input.txt') ;
  reset(inp) ;
  assign(out, 'output.txt') ;
  rewrite(out) ;
  if Test then writeln('Initialized')
  end { Init } ;
procedure Fini ;
  begin
  close(inp) ;
  close(out)
  end { Fini } ;
{Problema}
const
  MaxM = 50 ;
  MaxN = 50 ;
type
  Row = 1..MaxM ;
  Column = 1..MaxN ;
  Direction = (west, north, east, south) ;
  Module = record
    wall: array [Direction] of boolean ;
    nr: integer ; { room number, -1 if unknown }
    end { Module } ;
var
  M: Row ;
  N: Column ;
  Map: array [Row, Column] of Module ;
procedure ReadInput ;
  { read M, N, and Map ; initialize room numbers to -1 }
  var r: Row ; c: Column ; w: integer ; d: Direction ;
  begin
  readln(inp, M, N) ;
 if Test then writeln('Number of rows is', M:1,',number of columns',N:1);
  for r := 1 to M do begin
    for c := 1 to N do with Map[r, c] do begin
      read(inp, w) ; { w encodes the walls of module Map[r, c] }
      for d := west to south do begin
        wall[d] := odd(w) ;
        w := w div 2
        end { for d } ;
      nr := -1
      end { for c with Map } ;
    readln(inp)
    end { for r } ;
  if Test then writeln('Input read') ;
  end { ReadInput } ;
procedure WriteCastle ;
  { write Map to output }
  var r: Row ; c: Column ;
  begin
  for c := 1 to N do with Map[1, c] do
    if wall[north] then write(' _') else write('  ') ;
  writeln ;
  for r := 1 to M do begin
    for c := 1 to N do with Map[r, c] do begin
      if (c = 1) then if wall[west] then write('|') else write(' ') ;
      if wall[south] then write('_') else write(' ') ;
      if wall[east] then write('|') else write(' ')
      end { for c with Map } ;
    writeln
    end { for r }
  end { WriteCastle } ;
type
  RoomNumber = 0..MaxM*MaxN ;
var
  rooms: RoomNumber ; { number of rooms completely painted }
  area: array[RoomNumber] of integer; {area[n] is area of room nr. n}
  maxarea: integer ; { maximum room area }
procedure PaintMap ;
  { paint the map }
  procedure PaintRoom(r: Row; c: Column) ;
{if Map[r, c] is unpainted then paint it and all modules connected to it}
begin
    with Map[r, c] do
      if nr = -1 then begin
        nr := rooms ; inc(area[rooms]) ;
        if not wall[west]  then PaintRoom(r, c-1) ;
        if not wall[north] then PaintRoom(r-1, c) ;
        if not wall[east]  then PaintRoom(r, c+1) ;
        if not wall[south] then PaintRoom(r+1, c)
        end { if }
end { PaintRoom } ;
var r: Row ; c: Column ;
begin
  rooms := 0 ; maxarea := 0 ;
  for r := 1 to M do
    for c := 1 to N do
      if Map[r, c].nr = -1 then begin
        area[rooms] := 0 ;
        PaintRoom(r, c) ;
        if area[rooms] > maxarea then maxarea := area[rooms] ;
        rooms := succ(rooms)
        end { if }
end { PaintMap } ;
procedure WriteColors ;  
  { write Map colors to output }
  var r: Row ; c: Column ;
  begin
  for r := 1 to M do begin
    for c := 1 to N do write(Map[r, c].nr:2) ;
    writeln
    end { for r }
  end { WriteColors } ;
var
  bestrow: Row ; bestcol: Column ; bestdir: Direction ;
procedure BestWall ;
  var r: Row ; c: Column ; maxp: integer ;
  procedure Update(k1, k2: RoomNumber; d: Direction) ;
    var p: integer ;
    begin
    if k1 = k2 then p := area[k1] else p := area[k1] + area[k2] ;
    if p > maxp then begin
      maxp := p ; bestrow := r ; bestcol := c ; bestdir := d
      end { if }
    end { Update } ;
  begin
  maxp := 0 ;
  for r := 1 to M do
    for c := 1 to N do with Map[r, c] do begin
  if (r <> M) and wall[south] then Update(nr, Map[r+1, c].nr, south) ;
  if (c <> N) and wall[east]  then Update(nr, Map[r, c+1].nr, east) ;
      end { for c with Map }
end { BestWall } ;
procedure ComputeAnswer ;
begin
  PaintMap ;
  if Test then WriteColors ;
  BestWall
  end { ComputeAnswer } ;
procedure WriteOutput ;
  begin
  if Test then begin
    writeln('Number of rooms = ', rooms:1) ;
    writeln('Maximum room area = ', maxarea:1) ;
    writeln('Best wall to remove = ', bestrow:1, ' ', bestcol:1, ' ',
bestdir:1)
    end { if Test } ;
  writeln(out, rooms:1) ;
  writeln(out, maxarea:1) ;
  write(out, bestrow:1, ' ', bestcol:1, ' ') ;
  case bestdir of
    south: writeln(out, 'S') ;
    east: writeln(out, 'E') ;
    end { case }
  end { WriteOutput } ;
begin
Init ;
ReadInput ;
if Test then WriteCastle ;
ComputeAnswer ;
WriteOutput ;
Fini
end.

      Variante ale problemei:
  Este tentant de rezolvat aceast[ problem[ cu unele restricii.
De exemplu, s[ se poat[ considera un castel n care num[rul de camere s[ nu poat[ fi stocat complet
n program. Cum ar fi un caz n care pe latura est-vest pot fi maxim 1000 module, iar pe latura nord-sud,
maxim 10.000 module.
      Sau, o limitare superioar[ la 100 a num[rului de camere.
      S[ se modifice programul astfel ca s[ determine toate camerele de suprafa[ maxim[ i toate
zidurile de potenial maxim, cu indicarea perechilor de camere care sunt unite.
s[ se verifice dac[ printre zidurile cu potenial maxim exist[ unul care separ[ dou[ camere care nu au
arie maxim[.
      Cnd verific[m programele scrise pentru problem[, este necesar s[ construim teste ca date de
intrare. S[ se scrie un program care pentru harta unui castel (aa cum este dat[ de procedura
WriteCastle genereaz[ o codificare numeric[ a zidurilor, conform intr[rii cerute de problem[.

      Teste:
   Au fost 5 teste (1-5), fiecare din ele notat cu cte 6 puncte. Timpul de rulare pentru fiecare test a fost
de 30 secunde.
Test 0:
 _ _ _ _ _ _ _
|_  |_  |  _  |
| |_  |_| |_| |
|  _ _| |_| | |
|_|_ _ _ _ _|_|
.............................
Test 1:
 _ _ _ _ _
|_ _| |_  |
|  _| |_| |
| |_| |  _|
|_ _|_|_|_|
.............................
Test 2:
 _ _ _ _ _ _ _ _ _ _
|  _ _   _ _   _ _  |
|   |   |   |   |   |
|   |   |   |   |   |
|  _|_  |_ _|  _|_  |
|_ _ _ _ _ _ _ _ _ _|
.......................................
Test 3:
 _ _ _ _ _ _ _ _ _ _
|_ _ _ _| |  _      |
|       | |         |
|       | |         |
|       |_|_ _ _ _  |
|       | |_ _ _ _|_|
|       | | |       |
|       | | |       |
|       |_| |       |
|       | | |       |
|_ _ _ _|_|_|_ _ _ _|
................................
Test 4:
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
|_ _|   |   |   |   |   |_    |
|  _ _|_ _|_ _|_ _|_ _|_  |   |
|_| |_ _ _ _ _ _ _ _|_  | |   |
|_  |  _ _ _ _ _ _ _  | |_|   |
| |_| | |_ _   _ _| | |_| |_ _|
|  _| |  _ _| |_ _  |_  |  _  |
|_| | | |  _ _ _  | |  _|_ _ _|
|_  | |_| |  _  | |_| |  _ _  |
| |_|  _  |  _  |  _  | |  _ _|
|  _| | | |_ _ _| | | | |_ _  |
|_| |_| |_ _   _ _|_|_| |  _ _|
| | |_|_ _ _| |_ _|_ _| |_ _  |
| |_| | |_ _ _ _ _| |  _|  _ _|
|_|_|_|_|_ _ _|_ _ _|_ _ _ _ _|
........................................
Test 5:
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| |_| |  _|_ _ _ _|       |_| | | | |_    |  _    |_|  _|  _ _ _  |_ _   _| | |_ _|  _| | |_|_ _|_| |
|  _|_   _ _|_| | |_|_ _ _     _|_      |_|  _| |_  |_ _|_| |_| |_|  _      |_|_|_  |_|_|_|_ _ _  | |
|_|_|_ _ _|_  | |_|   |_|_ _|  _|_|  _|_  |   |  _  |_  |  _    | |_|  _|_|_|   |_|_    |  _| | |  _|
| |  _| |  _| |       |_|_ _|_|_     _|_ _|    _  |    _| |_| |  _ _|_|_      |   |_ _|_|  _|_ _| | |
|_   _|  _   _    |   |    _| | | |_|_ _|  _|_ _  |_   _|        _  |_ _  |   |_   _|_|_|_ _ _ _   _|
| |_  |_|  _|_|_  | |_|   |_|  _  |         | |_| |_|_   _|  _| |_  | | |  _ _  | |_ _  |_|_|_ _| | |
|_| | |_|_| |_  | |_|_|_|    _|_| |_ _ _| |      _ _ _  |_| |_|_|_  | |  _|_|  _|_    |_ _| |   | |_|
|_ _    |_|_   _ _|_  |  _|_      |_  |_|_ _  |  _| |_| |_|   |_     _   _|_| |_| |_| |_|_|_ _   _| |
| | |_|_|   |_|_     _|_ _|_ _    |_ _ _|  _|   |  _|   |   |_ _   _| | | |_ _|_|  _ _ _ _| |_ _    |
|_ _     _ _   _|_  |_| |   |_ _ _  |_|_| | |_  |_| | | |_   _ _ _ _   _ _| |_ _ _|_|  _     _  | |_|
|_| | |_|_|_ _| |_|_  | |_ _| | |_ _  |_      |_|_ _|_ _|_ _ _ _|_ _ _  |  _| |_   _| |_  |_|  _ _|_|
|_| |   |   |_| |       |_ _|_   _|_    | |_| |_  |_ _ _|_ _ _|_|_|   |_|_|_  | |   |        _|_|_ _|
|_|  _| | |_| |     | | | |_  | |_ _ _ _| |  _| | |_|_|_|_|_ _|_|_|_| | |_  | |_|_|      _ _     _| |
|_ _| |  _  |  _|_  |  _| |_ _  |    _ _|_    |_| |_|_|_|     |      _  | |_    |_| |   |_  |_     _|
| |_ _   _ _  | |     |_|_ _ _      |  _  |_|_|_ _ _ _|_ _| |_  |  _  |_|_  |_|    _|_ _|   |       |
|  _ _|_ _  |  _|_ _| |_| |  _ _| |_| |_| |_   _| |  _ _| | | |  _|_|_|  _|_ _  |  _| |  _|_ _|  _| |
| |_  |_ _|   | | |_|   | |_   _|_ _|_ _     _ _|_ _   _|_|_  | |_   _ _  |  _|_  |  _|_  |   |_|_|_|
|_|_| |_   _|  _| |_|_ _ _ _ _ _|_ _| |_   _|_ _  |_ _| | | |_|_ _  |_| | |_|  _|_|  _|_ _   _  |_| |
|    _ _| |     |_|_|_      | |  _| |_|   |_ _|_   _  |_|   | |_|_  |_ _ _  |   |_|_ _  |  _|_|   | |
|  _ _ _|_  |   |     |  _ _  | |_| |_|_      |_ _|   | |   |_ _      |_ _|  _|_  |    _ _        | |
|_  | |   |  _ _ _|_ _  |  _ _   _|_|    _| |_  |_| |_       _   _| |_  |     |  _ _    |_| |_|   |_|
| |_ _  |_|_     _|   |  _   _|_|_|_|  _ _   _ _|  _|      _|_|_  |  _   _|_|   |    _   _   _   _ _|
|_|_ _  |_  |_|   | | |   |   | |_ _| |_| | | |_   _|_  |_|_   _|_ _|    _|   |_  |     |_ _ _| |_|_|
|_    |    _|  _  | |    _  |_|         |  _ _|   |_  |_  |  _ _   _|   |_|_  |   | | |  _  | |_|_|_|
|  _|_  |_    | | | |_| |   |_ _ _ _ _|   |_ _    |  _   _ _| |_   _ _  |_ _ _ _|_|_|  _|_|   |_   _|
| |     |_| |_|_|  _  |_|      _|    _| |_  | | | | |_    | |_|  _|_ _  | |_  |_ _ _  |_|_    |_|  _|
|   |_ _|   | |    _ _ _ _|     |_| |_|_  |_|_ _|    _  |_   _|_| |_|_ _|  _|   |   |_ _|_  |_| |_| |
|_| |_|_   _ _|         |_  |_    |_ _ _|_|   | | |   | |_  |_   _ _|   |_|_|  _|   |_ _| |_| |_ _  |
|_ _| |_ _|_|  _| |_|  _| |_ _|    _ _       _ _ _| | |_| | |_|_  |_  |  _|   |  _ _  | |  _|_|_   _|
|  _ _|        _     _|    _  |_ _ _ _   _ _| |_ _|  _|  _| |    _ _|  _   _ _|  _|_ _ _|_  |_|_ _  |
|_ _|_|_| |_|_|_| |_|   | |_| |_ _ _| |   |_|_     _  |_|_  |_|_ _ _|_  |_ _ _  |  _ _ _ _ _   _|  _|
|_|  _|_    |_|_|_|_|_ _   _  | |_   _  |_|  _   _|_   _        |  _|_  |    _|_|_|_ _|   |  _ _  | |
| |_  |_ _|_|    _  |_| |_|_ _  | |_|   |_| |_| | |  _  |   | |_   _ _  |_ _ _ _|   | |_|  _ _  |   |
|_ _|_|   | |   |_ _ _|   |_  |_  |   | |_|_ _|  _  |_|_     _| |_| |  _| |_|   | |_|_ _|_|_ _|_  | |
|_|_|_|_|_|_  |_|_|_ _|_   _|_  | | |_ _|_    |_  | |_|_   _    |_ _|  _ _|_|_|  _  |        _ _ _| |
|   |_|  _ _ _| |  _    |  _|_|_| |_|_|_   _ _  |_| |_|  _  |_|_|_ _|_ _| |_|_  | |_  |_|_ _|  _|_| |
| |_  |_ _|  _|     |_  |_  |_|_|_| |_|_ _|_ _| |  _|  _   _ _ _ _ _ _|  _  |_|_   _ _|_  | |_   _  |
|_   _|_|_ _ _|     | |_|     |_  |_   _ _|_|_  |_   _ _|_  |_  |_        |_|_|_|     |   |_ _|_|_  |
|   |_ _|  _    |_  | |_|_ _|   |_| |_   _| |_|_ _ _|_ _|_|_ _|_ _|_ _|   |_|  _  | | |   |    _ _| |
|_  |_ _  |_ _|_|_| |    _   _|  _  |_  |_|_|_   _ _    | |  _|_      |_| |_ _| |_ _|_ _|_|_|_ _ _ _|
|_|_ _|_|_    | |_|_| |_ _|_|  _| |_|   |_| |  _|_  |_  |_|  _ _| |  _|    _|_|_ _  |_    |_|_| |_  |
| | | |_|    _  |  _|_   _ _|  _|_   _    | |     |_ _  |  _      |_|_    |_  |_|       |_  |_ _    |
|_|     | |_|_ _  |  _  | |_|  _|  _  |_   _ _ _|   |_|_   _       _|_ _| |_|_   _|_ _  |_ _|_| | |_|
| |   |  _|_ _ _|_ _|  _ _|_  |_|  _| | |_  |_|_|_ _ _|    _  | |   |_|_|_|_    | | |_|_|_|_|     |_|
|   |   |_| |  _| | |_  |_|_ _   _    |_   _  |_|_| |_|_| |  _|_|   |   | |_ _| |_| |_    |_|    _ _|
|_|_ _ _| |    _|_|_ _|  _    |  _|_|   |    _ _  |  _ _   _|_ _|    _|  _|_   _|_|  _  |  _ _| |_|_|
|     | |_| |_|_  |_ _|_  |  _    |_ _|   | |_ _|_ _ _ _|_|  _| |_| |   | |  _|_| |_     _| | |_|_  |
| |_ _|   |   |  _|_|_ _   _| |_|_|    _ _| |  _|_| |  _| |_|_  | | | |_|_  |_  | |  _|      _| |_|_|
|  _|_|_| |_|  _|  _ _|_ _   _    |  _|_  | |_   _  | | |_ _|      _ _| | |_|_|_| |_ _  |_   _ _  |_|
|_|_ _|_|_ _ _ _|_|_|_ _ _|_ _|_ _ _|_|_ _ _ _ _|_|_|_|_|_|_ _|_ _|_ _|_|_ _|_ _ _ _|_|_ _ _|_|_|_ _|
......................................
Test 0
4
7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13
-----------------------
Test 1
4
5
11 14 7 11 6
3 14 5 15 5
5 15 5 3 12
9 14 13 13 15
---------------------
Test 2
5
10
3 10 10 2 10 10 2 10 10 6
1 6 3 4 3 6 1 6 3 4
1 4 1 4 1 4 1 4 1 4
1 12 9 4 9 12 1 12 9 4
9 10 10 8 10 10 8 10 10 12
-----------------------------------
Test 3
10
10
11 10 10 14 7 3 10 2 2 6
3 2 2 6 5 1 2 0 0 4
1 0 0 4 5 1 0 0 0 4
1 0 0 4 13 9 8 8 8 4
1 0 0 4 7 11 10 10 14 13
1 0 0 4 5 7 3 2 2 6
1 0 0 4 5 5 1 0 0 4
1 0 0 4 13 5 1 0 0 4
1 0 0 4 7 5 1 0 0 4
9 8 8 12 13 13 9 8 8 12
---------------------------------------
Test 4
14
15
11 14 3 6 3 6 3 6 3 6 3 6 11 2 6
3 10 12 9 12 9 12 9 12 9 12 9 6 1 4
13 7 11 10 10 10 10 10 10 14 11 6 5 1 4
11 4 3 10 10 10 10 10 10 10 6 5 13 1 4
7 13 5 7 11 10 2 10 14 7 5 13 7 9 12
1 14 5 1 10 14 5 11 10 4 9 6 1 10 6
13 7 5 5 3 10 8 10 6 5 3 12 9 10 12
11 4 5 13 5 3 10 6 5 13 5 3 10 10 6
7 13 1 10 4 1 10 4 1 10 4 5 3 10 12
1 14 5 7 5 9 10 12 5 7 5 5 9 10 6
13 7 13 5 9 10 2 10 12 13 13 5 3 10 12
7 5 15 9 10 14 5 11 14 11 14 5 9 10 6
5 13 7 7 11 10 8 10 14 7 3 12 3 10 12
13 15 13 13 11 10 14 11 10 12 9 10 8 10 14
----------------------------------------------------
Test 5:
50
50
7 15 7 3 14 11 10 10 14 3 2 2 6 15 7 7 7 7 11 2 6 3 10 2 6 15 3 14 3 10 10 10 6 11 10 2 14 7 7 11 14 3 14 7 7 15 11 14 15 7
1 14 9 0 10 14 15 7 7 13 9 8 8 2 0 12 9 0 2 4 13 1 14 5 9 6 9 14 13 7 15 7 13 3 10 0 2 4 13 15 11 4 15 13 13 11 10 10 6 5
13 15 11 8 14 11 6 5 13 3 6 15 11 12 1 14 15 1 12 9 6 1 6 1 10 4 11 6 3 8 2 4 7 13 3 12 13 13 3 6 15 9 2 6 3 14 7 7 1 12
7 3 14 7 3 14 5 1 2 0 4 15 11 14 13 11 2 0 14 11 12 1 0 8 6 1 2 12 5 15 5 1 8 14 13 11 2 2 4 1 6 11 12 13 1 14 9 12 5 7
9 0 14 1 8 2 8 0 4 1 4 3 2 14 7 7 5 13 11 14 3 12 9 10 4 9 0 14 1 2 0 0 10 6 11 10 4 1 4 9 0 14 15 15 9 10 10 10 0 12
7 9 6 13 3 12 15 9 4 5 13 1 4 15 1 8 4 3 2 2 0 6 7 15 5 15 9 2 12 1 12 5 11 4 7 7 1 8 8 6 5 11 10 6 15 15 11 14 5 7
13 7 5 15 13 7 11 6 5 13 15 13 1 2 12 15 5 9 8 12 5 1 0 2 8 10 10 4 15 5 15 13 11 4 5 1 12 15 3 12 9 2 6 9 14 7 3 6 5 13
11 8 0 6 15 9 2 8 12 11 6 3 12 9 2 2 4 11 6 15 9 8 4 1 14 7 15 5 15 1 6 11 2 0 8 0 14 15 5 15 7 13 5 15 15 9 8 0 12 7
7 7 13 13 3 6 13 11 2 2 12 9 14 11 8 0 4 11 8 14 3 14 1 4 3 12 3 4 3 4 9 10 0 12 7 5 7 11 12 15 1 10 8 10 14 7 11 8 2 4
9 8 2 2 8 8 2 14 9 4 15 7 3 6 11 8 8 6 15 15 5 7 9 4 13 7 5 5 9 0 10 10 8 10 0 8 12 7 11 10 12 15 3 10 2 0 10 6 5 13
15 7 5 13 15 11 12 7 15 9 6 5 9 12 7 7 11 8 6 11 0 0 6 13 11 12 9 12 11 8 10 14 11 10 8 6 3 12 7 11 2 14 5 11 4 13 3 8 12 15
15 5 1 6 3 6 15 5 3 2 0 4 11 14 9 0 14 11 0 6 5 13 5 11 6 11 10 14 11 10 14 15 15 3 6 13 13 11 4 7 1 6 1 2 0 2 12 15 11 14
15 1 12 5 5 13 7 1 0 4 5 5 7 11 6 5 11 10 8 12 5 3 12 7 5 15 15 15 15 11 14 15 15 13 5 7 11 6 5 13 13 1 0 0 8 8 2 2 14 7
11 12 7 1 8 6 1 12 9 4 1 12 5 11 8 4 3 2 10 14 9 0 6 13 5 15 15 15 3 2 6 3 2 2 8 4 7 9 0 6 15 5 1 4 11 6 9 0 2 12
7 11 8 0 10 8 4 7 3 0 4 15 9 10 10 0 0 4 3 10 6 13 13 11 8 10 14 11 12 5 9 4 1 8 6 13 9 6 13 1 2 12 9 12 3 4 3 0 0 6
1 10 14 9 10 6 1 12 9 12 5 15 7 3 10 12 5 13 5 15 5 11 2 14 7 3 10 14 7 5 7 1 12 15 13 3 14 9 10 4 1 14 7 3 12 9 12 1 12 5
5 11 6 11 14 1 4 7 7 15 1 6 5 9 2 14 9 14 9 10 0 2 8 14 9 8 2 14 13 9 4 5 11 2 10 8 6 3 14 9 4 3 12 9 6 3 6 13 15 13
13 15 5 11 2 12 1 12 5 15 9 8 8 10 8 14 11 14 7 11 0 12 11 10 6 11 12 7 7 7 13 9 10 4 15 7 5 13 3 14 13 1 14 11 8 0 8 6 15 7
3 2 8 14 5 3 0 6 13 15 11 2 2 6 7 3 14 7 13 3 4 11 14 11 0 10 6 13 1 4 7 15 11 4 11 8 8 6 1 6 15 9 10 6 3 12 15 1 6 5
1 8 10 14 9 4 1 4 3 2 6 1 8 8 4 5 15 5 15 9 0 2 6 11 12 3 4 7 1 4 9 10 2 0 6 11 14 1 12 9 6 3 2 8 8 2 2 0 4 5
9 6 7 3 6 1 8 8 12 9 8 4 3 10 8 0 14 13 3 2 12 5 9 6 15 5 9 0 0 0 10 2 12 5 9 6 3 0 6 3 8 8 0 6 15 5 13 1 4 13
7 9 8 4 13 9 2 2 14 3 6 1 8 2 14 13 15 15 1 8 10 0 10 12 3 12 3 0 0 12 15 9 6 1 10 0 12 13 1 4 3 2 8 0 10 0 10 0 8 14
13 11 10 4 11 6 13 1 6 5 5 1 6 1 6 7 11 14 5 15 7 5 7 11 0 14 9 4 13 11 2 14 9 12 3 0 14 3 4 9 4 1 2 4 11 8 14 5 15 15
11 2 6 1 2 12 3 8 4 5 1 0 8 4 13 1 2 2 0 6 1 8 12 3 4 11 6 9 6 3 8 10 2 14 1 4 15 9 4 3 4 5 5 1 10 6 7 13 15 15
3 12 9 4 9 2 4 7 5 5 13 5 3 4 11 8 8 8 12 1 4 11 10 0 4 3 8 2 8 12 7 11 0 10 8 4 11 10 8 12 13 13 1 12 15 1 4 11 2 14
5 3 2 4 15 5 13 13 1 8 6 13 1 0 2 14 3 2 14 5 9 6 7 5 5 5 11 0 6 7 13 3 12 11 10 4 7 11 6 11 10 10 4 15 11 0 4 15 1 14
1 4 9 12 3 4 7 3 0 10 8 10 12 1 0 6 13 5 15 9 6 13 9 12 1 0 10 4 9 0 14 13 7 15 11 12 1 14 1 6 3 6 9 14 11 4 13 7 13 7
13 5 15 11 0 8 12 1 0 2 2 6 11 4 9 0 6 9 10 14 13 3 6 7 5 1 6 5 11 4 11 2 8 14 3 6 13 15 1 12 1 4 11 14 7 13 7 9 10 4
11 12 7 11 12 15 3 12 5 13 1 12 7 9 14 1 0 10 10 2 2 0 8 8 12 5 5 13 7 5 15 9 6 11 4 1 14 3 4 3 8 8 6 7 1 14 13 11 2 12
3 10 12 3 2 2 0 10 0 2 12 3 0 10 6 9 8 10 10 0 8 12 7 11 14 1 12 3 12 5 3 2 8 14 1 8 2 8 12 1 14 11 8 12 9 6 15 11 8 6
9 14 15 13 5 13 13 15 5 13 3 4 5 15 5 11 10 14 7 1 6 15 9 2 2 8 6 13 11 4 13 9 10 14 9 6 9 10 10 4 3 10 10 10 10 8 2 14 3 12
15 3 14 11 0 6 15 15 13 15 9 8 0 10 4 7 11 2 8 4 13 3 10 0 12 11 0 10 2 0 2 6 3 14 11 4 3 2 14 13 13 11 14 3 6 3 8 10 4 7
7 9 6 11 12 13 3 2 10 6 15 7 13 11 8 4 7 13 3 4 15 5 15 5 7 3 8 6 1 4 5 9 0 10 10 4 9 8 10 14 3 6 7 13 1 8 10 6 1 4
9 14 13 3 6 7 1 4 11 8 14 1 6 11 6 9 4 3 4 5 15 9 14 1 8 4 15 9 0 0 12 7 13 7 3 12 7 15 3 6 5 13 9 14 13 11 14 9 4 5
15 15 15 13 13 9 4 13 15 11 14 9 0 14 9 6 5 5 9 12 11 2 6 9 6 5 15 11 0 8 2 4 11 12 1 10 12 15 13 1 8 6 3 2 2 2 10 10 12 5
3 6 15 3 10 10 12 7 3 10 2 6 1 14 15 13 5 13 15 11 2 8 8 6 13 5 15 3 8 6 13 13 11 14 9 14 7 15 11 4 7 9 4 13 9 12 3 14 15 5
5 9 6 9 14 3 14 1 0 6 9 4 9 6 15 15 13 7 15 11 12 11 14 5 3 12 3 8 2 8 10 10 10 10 14 3 8 6 15 9 0 10 12 11 6 7 9 2 10 4
9 2 12 15 11 8 14 1 0 4 7 13 3 0 6 11 6 9 2 10 14 15 11 4 9 2 8 14 9 6 11 6 11 2 2 0 6 13 15 15 1 2 6 3 4 9 14 13 11 4
3 4 11 14 3 10 2 4 9 4 5 15 9 12 1 6 13 7 9 2 14 7 15 9 10 12 11 14 15 9 14 9 14 9 12 1 4 15 3 10 4 5 5 1 4 3 2 10 14 5
9 4 11 10 4 11 12 13 15 5 1 2 10 2 12 1 10 4 11 4 15 13 11 2 10 10 2 6 7 3 14 11 2 2 6 13 5 11 12 7 9 12 9 12 13 13 9 10 10 12
15 9 14 15 9 2 6 7 15 13 5 9 14 13 3 12 7 13 3 4 15 7 3 12 11 6 9 4 13 1 10 14 5 1 12 3 0 14 15 9 10 6 11 2 6 15 15 7 11 6
7 7 7 15 3 0 8 4 3 14 9 2 10 14 1 14 9 2 8 0 6 5 1 2 6 9 10 4 3 8 2 2 4 13 11 0 4 11 6 15 3 0 2 4 9 6 11 8 2 4
13 1 0 6 5 13 11 8 4 3 10 4 7 15 1 14 3 8 6 9 0 8 8 12 1 6 15 9 0 10 0 0 0 14 11 12 5 15 9 2 12 9 8 4 11 12 15 7 5 13
7 1 4 1 12 11 10 14 9 12 3 8 12 11 4 15 1 14 5 7 9 6 15 15 9 8 14 3 0 10 4 5 1 6 15 15 13 11 2 4 7 7 15 13 15 15 3 0 4 15
1 4 1 4 15 7 3 14 7 7 9 6 15 11 8 2 8 2 4 9 2 8 6 15 15 7 15 13 5 3 12 13 1 4 3 6 7 11 12 5 13 5 11 2 6 15 1 0 8 14
13 9 8 12 7 1 0 14 13 9 14 1 10 2 6 1 14 13 1 6 1 2 8 10 6 1 10 10 0 12 11 14 1 0 12 1 12 11 2 12 15 1 10 4 1 10 12 5 15 15
3 2 6 7 13 5 13 11 6 11 14 9 6 1 8 0 6 11 12 1 4 5 11 14 9 8 10 14 13 3 14 7 13 5 3 4 7 3 12 15 7 9 2 0 12 7 7 13 11 6
5 9 12 1 6 1 6 3 12 15 11 10 0 12 7 13 13 3 2 8 12 5 3 14 15 7 3 14 7 13 11 4 7 5 5 13 9 4 11 6 5 3 12 1 2 0 12 7 15 13
1 14 15 13 5 13 1 12 3 10 14 11 8 2 8 2 6 1 12 11 6 5 9 2 10 4 5 7 9 14 3 0 0 8 12 7 7 13 15 13 5 9 10 4 9 0 10 8 6 15
13 11 14 15 9 10 8 14 13 15 11 10 14 9 14 9 8 12 15 11 8 8 10 12 15 13 13 13 15 11 12 9 12 11 14 13 9 14 11 10 8 14 15 9 10 12 15 15 9 14
------------------------------------------------------------------------------

                 R[spunsuri la teste:
Ieire 0:
5
9
3 2 S
3 3 S
3 3 E
3 4 W
4 1 E
4 2 W
4 2 N
4 3 N
---------------------
Ieire 1:
7
6
1 3 E
1 4 W
3 3 E
3 4 W
4 3 E
4 4 W
------------------------
Ieire 2:
2
44
1 5 S
1 6 S
2 4 E
2 5 N
2 5 W
2 6 E
2 6 N
2 7 W
3 4 E
3 5 W
3 6 E
3 7 W
4 4 E
4 5 S
4 5 W
4 6 E
4 6 S
4 7 W
5 5 N
5 6 N
----------------------
Ieire 3:
9
36
5 10 S
6 10 N
-------------------------
Ieire 4:
27
55
7 12 S
8 11 E
8 12 N
8 12 W
9 11 E
9 12 W
10 11 E
10 12 W
11 11 E
11 12 W
--------------------------------
Ieire 5:
306
905
36 18 S
37 18 N
37 20 S
37 21 S
38 20 N
38 21 N
39 24 S
39 25 S
39 26 S
39 30 S
39 31 S
40 24 N
40 25 N
40 26 N
40 30 N
40 31 N
------------------------
